package consistenthash

import (
	"hash/crc32"
	"sort"
	"strconv"
)

//定义了函数类型 Hash，采取依赖注入的方式，允许用于替换成自定义的 Hash 函数，也方便测试时替换
//默认为 crc32.ChecksumIEEE 算法
type Hash func(data []byte) uint32

//Map 是一致性哈希算法的主数据结构，包含 4 个成员变量：
//Hash 函数 hash；
//虚拟节点倍数 replicas；
//哈希环 keys；
//虚拟节点与真实节点的映射表 hashMap，键是虚拟节点的哈希值，值是真实节点的名称。
type Map struct {
	hash Hash
	replicas int
	keys []int
	hashMap map[int]string
}

func New(replicas int ,fn Hash) *Map {
	m := &Map{
		hash:     fn,
		replicas: replicas,
		hashMap:  make(map[int]string),
	}
	if m.hash == nil {
		m.hash = crc32.ChecksumIEEE
	}

	return m
}

//添加真实节点/机器
func (m *Map) Add(keys ...string)  {
	for _,key := range keys {
		for i := 0;i < m.replicas;i++{
			hash := int(m.hash([]byte(strconv.Itoa(i)+key)))
			m.keys = append(m.keys,hash)
			m.hashMap[hash] = key
		}
	}
	sort.Ints(m.keys)
}

//选择节点
func (m *Map) Get(key string) string {
	if len(m.keys) == 0 {
		return ""
	}
	//log.Println(len(m.keys))
	hash := int(m.hash([]byte(key)))
	//Search函数采用二分法搜索找到[0, n)区间内最小的满足f(i)==true的值i
	idx := sort.Search(len(m.keys), func(i int) bool {
		return m.keys[i] >= hash
	})
	return m.hashMap[m.keys[idx%len(m.keys)]]
}